package airthmetic.exercise.arr;

/**
 * @Author douhy
 * @description 数组相关算法
 * @date 22/01/27
 */
public class array {

    // leetCode 35. 搜索插入位置
    public static int searchInsert(int[] nums, int target) {
        // 如果最后以为元素小于等于 target 返回num.length
        int length = nums.length;
        if (nums[length - 1] < target) return length;

        // 左边界  右边界
        int left = 0;
        int right = length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }

        return left;

    }


    // 88. 合并两个有序数组
    //    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
    //
    //    请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
    //
    //    注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
//        // 思路：
//        // 1. nums1数组元素数量对应数组下标 和 nums2数组元素数量对应数组下标 和 nums1数组长度对应数组下标  对应三个指针
//        // 2. 循环 根据nums1指针 对比 nums2指针 将更大的放到 数组长度对应数组下标指针上  指针--
//
//        int p1 = m - 1;
//        int p2 = m - 1;
//        int current = nums1.length - 1;
//
//        while (p2 >= 0) {
//            if (p1 >= 0 && nums2[p2] < nums1[p1]) {
//                nums1[current--] = nums1[p1--];
//            } else { // p1 < 0 || nums2[p2] >= nums1[p1]
//                nums1[current--] = nums2[p2--];
//            }
//        }

            if (nums1.length == 0){
                nums1 = nums2;
                return;
            }

            if (nums2.length == 0){
                return;
            }

            int[] returnArr = new int[nums1.length + nums2.length];
            int n1=0;
            int n2=0;
            for (int i = 0; i < returnArr.length; i++) {

                if (n1 >= m){
                    returnArr[i] = nums2[n2++];
                    continue;
                }
                if (n2 >= n){
                    returnArr[i] = nums1[n1++];
                    continue;
                }

                if (nums1[n1]<nums2[n2]){
                    returnArr[i] = nums1[n1++];
                } else{
                    returnArr[i] = nums2[n2++];
                }
            }
            nums1 = returnArr;
















    }

    // 75. 颜色分类
    public static void sortColors(int[] nums) {
        // 思路：
        // 1.三指针对应头尾和遍历下标
        // 2.循环结束条件是 当遍历指针小于右指针(2的下标) 退出循环 因为后面都是2

        int index = 0;
        int left = 0;
        int right = nums.length - 1;

        while (index <= right) {
            if (nums[index] == 0) {
                swap(nums, index++, left++);
            } else if (nums[index] == 1) {
                index++;
            } else { // nums[index] == 2
                swap(nums, index, right--);
            }
        }

    }

    // 27. 移除元素
    //    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
    //
    //    不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
    //
    //    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int begin = 0;
        int end = nums.length - 1;

        while (begin <= end) {
            if (nums[begin] == val) {
                nums[begin] = nums[end];
                nums[end] = 0;
                end--;
            } else {
                begin++;
            }
        }
        return begin;
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 面试题 16.16. 部分排序
    public static int[] subSort(int[] arrays) {
        // 思路： 找逆序对(从左向右的时候找最右最小, 从右向左的时候找最左最大)
        // 判断数组为空 返回 -1,-1
        if (arrays.length == 0 || arrays == null) return new int[]{-1, -1};

        int right = -1;
        int max = arrays[0];
        for (int i = 1; i < arrays.length; i++) {
            int temp = arrays[i];
            if (temp >= max) {
                max = temp;
            } else {
                right = i;
            }
        }

        // 如果遍历一遍还是-1说明顺序是正确的
        if (right == -1) return new int[]{-1, -1};


        int left = -1;
        int min = arrays[arrays.length - 1];
        for (int i = arrays.length - 2; i >= 0; i--) {
            int temp = arrays[i];
            if (temp <= min) {
                min = temp;
            } else {
                left = i;
            }
        }

        return new int[]{left, right};

    }

    // 977 有序数组的平方
    public static int[] sortedSquares(int[] nums) {
        // 思路：
        // 有一个不容易发觉的条件是  题中给定数组是非逆序的   (负数  0  正数)
        // new一个新数组   创建头尾指针 和新数组指针
        // 遍历判断 头尾数组数值平方更大的 放入新数组的尾部   相应指针进行 ++ 或 --  新数组指针--
        // 遍历结束条件为 头指针 > 尾指针
        int l = nums.length;
        int[] arr = new int[l];
        for (int i = 0, j = l - 1, pos = l - 1; i <= j; ) {
            if ((nums[i] * nums[i]) > (nums[j] * nums[j])) {
                arr[pos] = (nums[i] * nums[i]);
                i++;
            } else {
                arr[pos] = (nums[j] * nums[j]);
                j--;
            }
            pos--;
        }
        return arr;
    }


    // 169. 多数元素(时间复杂度O(n) 空间复杂度O(1))
    //    给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
    //
    //    你可以假设数组是非空的，并且给定的数组总是存在多数元素。
    public static int majorityElement(int[] nums) {
        Integer element = nums[0];
        int elementNum = 1;

        for (int i = 1; i < nums.length; i++) {

            if (elementNum == 0) {
                element = nums[i];
                elementNum++;
                continue;
            }
            elementNum += nums[i] == element.intValue() ? 1 : -1;
        }
        return element;
    }


    // 11.  盛最多水的容器
    //    给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
    //    找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
    //    返回容器可以储存的最大水量。
    //    说明：你不能倾斜容器。
    // 穷举法和双指针方法
    public static int maxArea(int[] height) {
        int max = 0;
        // 穷举法
      /*  // 拿到第一次循环的头
        for (int i = 0; i < height.length; i++) {
            // 从尾部往回走
            for (int j = height.length - 1; j > i; j--) {
                int area = (j - i) * Math.min(height[j], height[i]);
                max = area > max ? area : max;
            }
        }*/

        // 双指针
        int left = 0;
        int right = height.length -1;
        while (left != right){
            int area = (right - left) * Math.min(height[left], height[right]);
            max = area > max ? area : max;

            if (height[left] < height[right]){
                left++;
            }else{
                right--;
            }
        }
        return max;
    }



    //  283.移动零
    //        给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    //        请注意 ，必须在不复制数组的情况下原地对数组进行操作。
    // 两次循环 与 一次循环 写法
    public static void moveZeroes(int[] nums) {
     if (nums == null || nums.length < 2){
            return;
        }
        /*int p =0;
        for(int i = 0; i< nums.length; i++){
            if (nums[i] != 0){
                nums[p] = nums[i];
                p++;
            }
        }

        while (p < nums.length){
            nums[p] = 0;
            p++;
        }*/

       /* int p1 = 0;
        for(int i = 0; i < nums.length; i++){
            if (nums[i] != 0){
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1++] = temp;
            }
        }*/

        if(nums == nums || nums.length < 2){
            return;
        }
        int j = 0;
        for(int i = 0; i< nums.length; i++){
            if(nums[i] != 0){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j++;
            }
        }
    }

    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 4, 5, 6};
//        int target = 3;
//        System.out.println(searchInsert(nums, target));

//        int[] nums = {2, 1, 0, 0, 2, 1, 2};
//        sortColors(nums);


//        int[] ints = {5, 3, 1, 7, 9};
//        int[] ints1 = subSort(ints);
//        for (int i : ints1) {
//            System.out.println(i);
//        }


//        int[] ints = {-5, -3, 1, 7, 9};
//        int[] ints2 = sortedSquares(ints);
//        for (int i : ints2) {
//            System.out.println(i);
//        }


//        int[] nums = {2, 1, 0, 2, 2, 1, 2};
//        System.out.println(majorityElement(nums));

        int[] nums = {0,1,0,3,12};
        moveZeroes(nums);
        for (int num : nums) {
            System.out.println(num);
        }



    }

}
